package com.da.javatest.algorithm;

/**
 * @author chenlida
 * @date 2019/3/15 14:38
 * @description
 */
public class InsertSort {
    public static void main(String[] args) {
        new InsertSort().insertionSort(new int[] {3, 1, 2, 7, 6, 2, 4, 3});
        //System.out.println(new Insert().insertionSort2(new int[] {3, 1, 2, 7, 6, 2, 4, 3}));
    }

    // 插入排序，a 表示数组，n 表示数组大小
    private void insertionSort(int[] a) {
        int n = a.length;
        if (n <= 1) { return; }
        for (int i = 1; i < n; ++i) {
            int value = a[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; --j) {
                if (a[j] > value) {
                    a[j + 1] = a[j]; // 数据移动
                } else {
                    break;
                }
            }
            a[j + 1] = value; // 插入数据
        }
    }


    //private String insertionSort2(int[] nums) {
    //    int n = nums.length;
    //    if (n < 2) {
    //        return "error!";
    //    }
    //    for (int i = 1; i < n; i++) {
    //        int value = nums[i];
    //        int j = i - 1;
    //        for (; j >= 0; j--) {
    //            if (nums[j] > value) {
    //                nums[j + 1] = nums[j];
    //            } else {
    //                break;
    //            }
    //        }
    //        nums[j + 1] = value;
    //    }
    //    return Arrays.toString(nums);
    //}
}
